package fail;

public class DecodeWays91_NotPassed {

	public static void main(String[] args) {
		System.out.println(numDecodings("1212"));
	}
	
	public static int numDecodings(String s) {
		int length = s.length();
		if(length == 0 || s.startsWith("0"))
			return 0;
		int[] history = new int[length];
		int[] count = new int[length];
		history[0] = 1;
		count[0] = 1;
		for(int i = 1; i < length; i++) {
			history[i] = history[i - 1];
			count[i] = count[i - 1];
			char first = s.charAt(i - 1);
			char second = s.charAt(i);
            int value = Integer.parseInt(first + "" + second);
            System.out.print(value + " ");
            if(first != '0' && second != '0'){
                if(value <= 26) {
                	if(i - 2 > 0) {
                        history[i] += count[i - 2];
                	}else {
                		history[i] += 1;
                	}
                    count[i] += 1;
                }
            }
            else if(first != '0' && second == '0'){
                if(value > 26)
                    return 0;
                if(i - 2 >= 0){
                    char temp = s.charAt(i - 2);
                    if(Integer.parseInt(temp + "" + first) > 10 && Integer.parseInt(temp + "" + first) <= 26){
                        history[i] = history[i] - count[i - 1];
			            history[i - 1] = history[i];
	                    count[i] -= 1;
                    }
                }
            }
            else if(first == '0' && second == '0'){
                return 0;
            }
            System.out.println(history[i]);
		}
		return history[length - 1];
	}
}
